#include <vector>
#include <string>
using namespace std;
/*
 * @lc app=leetcode.cn id=131 lang=cpp
 *
 * [131] 分割回文串
 */

// @lc code=start
class Solution {
public:

    vector<vector<string>> res;

    // dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j]
    vector<vector<string>> partition(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), true));
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i + 1; j < s.size(); j++) {
                dp[i][j] = dp[i + 1][j - 1] && (s[i] == s[j]);
            }
        }
        vector<string> t;
        dfs(0, dp, t, s);
        return res;
    }

    void dfs(int index, vector<vector<bool>> & dp, vector<string> &now, string &s) {
        if (index == dp.size()) {
            res.push_back(now);
            return;
        }
        for (int i = index; i < dp.size(); i++) {
            if (dp[index][i]) {
                now.push_back(s.substr(index, i - index + 1));
                dfs(i + 1, dp, now, s);
                now.pop_back();
            }
        }
    }
};
// @lc code=end

